package com.njupt.graphTheory;

/**
 * @Author: wujiaming
 * @CreateTime: 2025/2/6 20:14
 * @Description: 208. 实现 Trie (前缀树)
 * @Version: 1.0
 */


public class Trie_208 {

    public class TreeNode{
        //判断是否是合法的单词
        boolean isWord;

        TreeNode[] children;


        public TreeNode(){
            this.isWord = false;
            this.children = new TreeNode[26];
        }
    }

    TreeNode root;

    public Trie_208() {
        this.root = new TreeNode();
    }

    /**
     * 【向字典树中插入单词】
     *
     * 按照word的字符从根节点开始一路往下走 ；
     *  遇到为null的节点，就new出新的节点
     *  如果节点已经存在，cur顺着往下走
     * @param word
     */
    public void insert(String word) {
        TreeNode cur = root;
        char[] charArray = word.toCharArray();

        for (int i = 0; i < charArray.length; i++) {
            int c = charArray[i] - 'a';
            if(cur.children[c] == null){
                cur.children[c] = new TreeNode();
            }
            cur = cur.children[c];
        }
        cur.isWord = true; //表示这个单词结束
    }

    /**
     * 【判断一个word在字典树中是否存在】
     *
     * 按照word的字符从根节点一直尝试往下走
     *  如果走到了null，说明这个word不是前缀树的任何一条路径，返回false
     *  如果按照word顺利走完，要判断此时的cur是否为单词的末端；如果是返回true，如果不是返回false（说明只是一个单词的前缀）
     * @param word
     * @return
     */
    public boolean search(String word) {
        TreeNode cur =  root;
        char[] charArray = word.toCharArray();
        for (int i = 0; i < charArray.length; i++) {
            int c = charArray[i] - 'a';
            if(cur.children[c] == null){
                return false;
            }
            cur = cur.children[c];
        }
        return cur.isWord;
    }

    /**
     * 【判断prefix是否是一个单词的前缀】
     *
     * 根据prefix的字符从根节点一路往下走；
     *  如果遇到了null说明不是前缀树的任何一条路径 返回false
     *  知道单词走完了，直接返回true
     * @param prefix
     * @return
     */
    public boolean startsWith(String prefix) {
        TreeNode cur = root;
        char[] charArray = prefix.toCharArray();
        for (int i = 0; i < charArray.length; i++) {
            int c = charArray[i] - 'a';
            if(cur.children[c] == null){
                return false;
            }
            cur = cur.children[c];
        }
        return true;
    }
}
